class Solution:
    def fib(self,n):
        d = {}
        def recur(n):
            if n < 0:
                return
            if n == 0 or n == 1:
                return 1
            if n in d:
                return d[n]
            else:
                d[n] = recur(n-1)+recur(n-2)
            return d[n]
        return recur(n)


s = Solution()
print s.fib(9) #55
